#include <stdio.h>
#include <string.h>

#include "dijkstra.h"

/* increase shortest path
 * src:	index of start vetex
 * D:	shortest path table from src to each vetex
 * P:	previous vetex fited D
 */
int dijkstra(unsigned int src, unsigned short * D, unsigned int * P)
{
	if(src >= VNUM){
		return -1;
	}

	//CLOSED SET
	unsigned char S[VNUM] = {0};
	unsigned int snum = 0;
	memset(S, 0, sizeof(S));

	//init <src, i>
	int i;
	for(i = 0; i < VNUM; i ++){
		D[i] = A[src][i];
		P[i] = src;
	}
	P[src] = _I_;
	S[src] = 1;

	//extend vetex from V to S, for VNUM - snum times
	for(snum = 1; snum < VNUM; snum ++){
		//min D[i]
		unsigned short	min = _I_;
		unsigned int	mi;
		//increase shortest path
		for(i = 0; i < VNUM; i ++){
			if(S[i] == 0 && D[i] < min){
				min = D[i];
				mi = i;
			}
		}
		if(min == _I_){
			break;
		}
		S[mi] = 1;

		//update D[i]
		for(i = 0; i < VNUM; i ++){
			if(S[i] == 0 && D[i] > A[mi][i]	+ min){
				D[i] = A[mi][i]	+ min;
				P[i] = mi;	//save the tail of arc
			}
		}
	}
	return 0;
}

int ppath(unsigned int dst, unsigned int * P)
{
	unsigned int stack[VNUM];
	int i;
	for(i = 0; i < VNUM - 1; i ++){
		stack[i] = dst;
		dst = P[dst];
		if(dst == _I_){
			break;
		}
	}
	for(; i >= 0; i --){
		printf(i>0?"%u->":"%u\n", stack[i]);
	}
	return 0;
}

int main()
{
	//SHORTEST PATH
	unsigned short D[VNUM] = {0};
	unsigned int P[VNUM] = {0};
	unsigned int src = 4;
	if(dijkstra(src, D, P) < 0){
		return -1;
	}
	int i;
	for(i = 0; i < VNUM; i ++){
		printf("%u -> %u : %u\t", src, i, D[i]);
		ppath(i, P);
	}
	return 0;
}

